package _18_剑指OfferII;


// 字典树寻找
public class _064_剑指OfferII神奇的字典2 {

    Trie first = new Trie();

    public _064_剑指OfferII神奇的字典2() {

    }

    public void buildDict(String[] dictionary) {
        for (String s : dictionary) {
            insert(s);
        }
    }

    public boolean search(String searchWord) {
        return findButDiffOne(searchWord, 0, first, 0);
    }


    private void insert(String word) {
        Trie node = first;
        int len = word.length();
        for (int i = 0; i < len; ++i) {
            char cur = word.charAt(i);
            Trie[] children = node.children;
            if (children == null) children = node.children = new Trie[26];
            Trie child = children[cur - 'a'];
            if (child != null) {
                node = child;
                continue;
            }
            Trie newNode = new Trie();
            // 新建
            children[cur - 'a'] = newNode;
            node = newNode;
        }
        node.isWord = true;
    }

    private boolean findButDiffOne(String word, int index, Trie trie, int diff) {
        if (diff > 1) return false;
        if (index >= word.length()) {
            return trie.isWord && diff == 1;
        }
        char cur = word.charAt(index);
        Trie[] children = trie.children;
        if (children == null) return false;
        for (char i = 'a'; i <= 'z'; ++i) {
            if (children[i - 'a'] == null) continue;
            if (findButDiffOne(word, index + 1, children[i - 'a'], diff + ((cur == i) ? 0 : 1)))
                return true;
        }
        return false;
    }

    static class Trie {

        boolean isWord;


        Trie[] children;
    }

}
